An Omega network is a network configuration often used in

parallel computing Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different fo ...

architectures Architecture is the art and technique of designing and building, as distinguished from the skills associated with construction. It is both the process and the product of sketching, conceiving, planning, designing, and constructing buildings o ...

. It is an indirect topology that relies on the perfect shuffle interconnection

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

Connection architecture

An 8x8 Omega network is a multistage interconnection network, meaning that processing elements (PEs) are connected using multiple stages of switches. Inputs and outputs are given addresses as shown in the figure. The outputs from each stage are connected to the inputs of the next stage using a perfect shuffle connection system. This means that the connections at each stage represent the movement of a deck of cards divided into 2 equal decks and then shuffled together, with each card from one deck alternating with the corresponding card from the other deck. In terms of binary representation of the PEs, each stage of the perfect shuffle can be thought of as a cyclic logical left shift; each bit in the address is shifted once to the left, with the most significant bit moving to the least significant bit. At each stage, adjacent pairs of inputs are connected to a simple exchange element, which can be set either straight (pass inputs directly through to outputs) or crossed (send top input to bottom output, and vice versa). For N processing element, an Omega network contains N/2 switches at each stage, and log₂N stages. The manner in which these switches are set determines the connection paths available in the network at any given time. Two such methods are destination-tag routing and XOR-tag routing, discussed in detail below. The Omega Network is highly blocking, though one path can always be made from any input to any output in a free network.

Destination-tag routing

In destination-tag routing, switch settings are determined solely by the message destination. The most significant bit of the destination address is used to select the output of the switch in the first stage; if the most significant bit is 0, the upper output is selected, and if it is 1, the lower output is selected. The next-most significant bit of the destination address is used to select the output of the switch in the next stage, and so on until the final output has been selected. For example, if a message's destination is PE 001, the switch settings are: upper, upper, lower. If a message's destination is PE 101, the switch settings are: lower, upper, lower. These switch settings hold regardless of the PE sending the message.

XOR-tag routing

In XOR-tag routing, switch settings are based on (source PE) XOR (destination PE). This XOR-tag contains 1s in the bit positions that must be swapped and 0s in the bit positions that both source and destination have in common. The most significant bit of the XOR-tag is used to select the setting of the switch in the first stage; if the most significant bit is 0, the switch is set to pass-through, and if it is 1, the switch is crossed. The next-most significant bit of the tag is used to set the switch in the next stage, and so on until the final output has been selected. For example, if PE 001 wishes to send a message to PE 010, the XOR-tag will be 011 and the appropriate switch settings are: A2 straight, B3 crossed, C2 crossed.

Applications

multiprocessing Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...

, omega networks may be used as connectors between the

CPUs A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, and ...

and their

shared memory In computer science, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Shared memory is an efficient means of passing data between progr ...

, in order to decrease the probability that the ''CPU-to-memory'' connection becomes a bottleneck. This class of networks has been built into the Illinois Cedar Multiprocessor, into the IBM RP3, and into the NYU Ultracomputer.

Examples

Omega network simulation in c

References